package binary_search;

/**题目：给定一个递增的数组，和一个目标值，要求返回这个值应该插入的位置
 * 二分搜索的变体
 * @Author Gavin
 * @date 2022.01.02 10:22
 */
public class array_2 {
    //Time:O(log(n)) Space:O(1)
    public static int solution(int[] nums ,int target){
        if(nums.length==0)return -1;
        int low=0,high=nums.length-1;
        while (low<=high){
            /**
             *注意，这里不使用（low+high）/2是因为怕内存溢出，
             * 有可能low的值和high的值都非常大了，然后两个相加就超过
             * int的最大值了
             */
            int mid=low+(high-low)/2;
            if(target<nums[mid])high=mid-1;
            else if (target>nums[mid])low=mid+1;
            else return mid;
        }
        //返回low是因为high是做mid-1的操作，会比预期位置少1
        //low会超过已有位置一位，high不会超过（比如求平方根的示例中返回的就是high）
        return low;
    }

    public static void main(String[] args) {
        int[] arr={0,1,2,3,5,6,7};
        System.out.println(solution(arr, 8));
    }
}
